package com.fantastic.tree;


import java.util.LinkedList;
import java.util.List;
import java.util.Queue;

/**
 * @author : fantastic
 * @date : 2024/5/17 12:08
 * @desc : this class for xxxxx
 **/
public class MaxDepth {

    /**
     * 深度优先搜索（DFS）
     *
     * @param root
     * @return
     */
    public static int maxDepthDFS(TreeNode root) {
        if (root == null) {
            return 0;
        }
        return Math.max(maxDepthDFS(root.getLeft()), maxDepthDFS(root.getRight())) + 1;
    }

    /**
     * 广度优先搜索（BFS）
     *
     * @param root
     * @return
     */
    public static int maxDepthBFS(TreeNode root) {
        if (root==null){
            return 0;
        }


        Queue<TreeNode> queue=new LinkedList<>();
        queue.offer(root);
        int depth = 0;
        while (!queue.isEmpty()){
            int size=queue.size();
            while (size-->0){
                TreeNode node = queue.poll();
                if (node.getLeft()!=null){
                    queue.offer(node.getLeft());
                }
                if (node.getRight()!=null){
                    queue.offer(node.getRight());
                }

            }
            depth++;
        }
        return depth;
    }


}
